package 算法;

import java.util.*;
class WordsFrequency {
    HashMap<String,Integer> hashMap = new HashMap<>();
    public WordsFrequency(String[] book) {
        for (String s : book) {
            if(hashMap.containsKey(s)){
                hashMap.put(s,hashMap.get(s)+1);
            }else {
                hashMap.put(s,1);
            }
        }
    }

    public int get(String word) {
        return hashMap.get(word);
    }
}
public class 有效的山脉数组 {
    public static void main(String[] args) {

        new 有效的山脉数组().pileBox(new int[][]{{1,1,1},{2,2,2},{3,3,3}});

    }

    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        Set<String> strings = new HashSet<>();
        for (String req_skill : req_skills) {
            strings.add(req_skill);
        }
        int[] count;
        Queue<Integer> strings1 = new LinkedList<>();
        while (strings.size() == 0){
            count = new int[people.size()];
            for (int i = 0; i < count.length; i++) {
                List<String> temp = people.get(i);
                int ma = 0;
                for (String s : temp) {
                    if(strings.contains(s)) ma++;
                }
                count[i] = ma;
            }
            int max = count[0];
            int maxin = 0;
            for (int i = 1; i < count.length; i++) {
                if(count[i] > max){
                    max =count[i];
                    maxin = i;
                }
            }
            strings1.add(maxin);
            for (String s : people.get(maxin)) {
                strings.remove(s);
            }
            people.remove(maxin);
        }
        int[] res = new int[strings1.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = strings1.poll();
        }
        Arrays.sort(res);
        return res;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        int hang = matrix.length-1,lie = 0;
        int l = matrix[0].length;
        while (hang >= 0 && lie < l){
            int i = matrix[hang][lie];
            if(i < target) lie++;
            else if(i > target) hang--;
            else
                return true;
        }
        return false;
    }
    public int pileBox(int[][] box) {
        //可以看成是信封问题，以0降序，1，2升序排列
        Arrays.sort(box, new Comparator<int[]>() {
            @Override
            public int compare(int[] ints, int[] t1) {
                if(ints[0] > t1[0]) return -1;
                else if(ints[0] < t1[0]) return 1;
                else {
                    if(ints[1] > t1[1]) return 1;
                    else if(ints[1] < t1[1]) return -1;
                    else {
                        if(ints[2] > t1[2]) return 1;
                        else if (ints[2] < t1[2])return -1;
                    }
                }
                return 0;
            }
        });
        int len = box.length;
        if (len==0) return 0;
        //hei[i] 表示以i为底的高度
        int[] hei = new int[len];
        hei[0] = box[0][2];
        for (int i = 1; i < len; i++) {
            int i1 = box[i][0];
            int i2 = box[i][1];
            int i3 = box[i][2];
            for (int j = i-1; j >= 0; j--) {
                if(box[j][0] > i1 && box[j][1] > i2 && box[j][2] > i3){
                    hei[i] = Math.max(hei[i],hei[j]+i3);
                }
            }
        }
        int max = 0;
        for (int i : hei) {
            if(max < i){
                max = i;
            }
        }
        return max;
    }
    public void setZeroes(int[][] matrix) {
        Set<Integer> hang = new HashSet<>(); //要清空的行信息
        Set<Integer> lie = new HashSet<>(); //要清空的列信息

        int len1 = matrix.length;
        if(len1 == 1)return;
        int len2 = matrix[0].length;
        for (int i = 0; i < len1;i++) {
            for (int i1 = 0; i1 < len2; i1++) {
                if(matrix[i][i1] == 0){
                    hang.add(i);
                    lie.add(i1);
                }
            }
        }
        for (Integer integer : hang) {
            for (int i1 = 0; i1 < len2; i1++) {
                matrix[integer][i1] = 0;
            }
        }
        for (Integer integer : lie) {
            for (int i1 = 0; i1 < len1; i1++) {
                matrix[i1][integer] = 0;
            }
        }
    }
    public static ListNode sortList(ListNode head) {
        List<ListNode> listNodes = new ArrayList<>();
        while (head != null){
            listNodes.add(head);
            head = head.next;
        }
        listNodes.sort(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode listNode, ListNode t1) {
                return t1.val - listNode.val;
            }
        });
        ListNode temp = new ListNode();
        head = temp;
        for (ListNode listNode : listNodes) {
            listNode.next = null;
            temp.next = listNode;
            temp = temp.next;
        }

        return head.next;
    }
    public static boolean validMountainArray(int[] A) {
        if(A.length < 3) return false;
        if(A[0] > A[1] || A[A.length-1] > A[A.length-2]) return false;
        boolean flag = true; //表判别，true代表大，false代表小
        for (int i = 1; i < A.length; i++) {
            if(A[i] > A[i-1]){
                //表示真在增加
                if(!flag) return false;
            }else if(A[i] < A[i-1]){
                //表示在减小
                if(flag) flag = false;
            }else {
                return false;
            }
        }
        return true;
    }
}
